MacHack 1997/MacHack 1997.toast/Presentations/Presentations ’96/Papers ’96/Book of Practical Objects/BasicObjects ƒ/CKeywords.cp

Text File | 1996-06-03 | 12.2 KB | 516 lines | [TEXT/CWIE]

#include "CKeywords.h"
#include "BoyerMoore.h"

    CKeywords::CKeywords(short longsPerReferenceItem, Boolean reuseHoles)
{
    fLongsPerReferenceItem = longsPerReferenceItem;
    fReuseEmptyHoles = reuseHoles;

    fTotalKeywords = 0;
    fFirstKeywordBlock = nil;

    fReferenceBlockSize = longsPerReferenceItem * sizeof(long);
}


    CKeywords::~CKeywords(void)
{
    // Delete all the keyword pages
    if (fFirstKeywordBlock != nil)
    {
        DeleteAllKeywords();
    }
}


long    CKeywords::GetKeywordCount(void)
{
    return (fTotalKeywords);
}


long    CKeywords::GetKeywordReferenceCount(long keywordID)
{

}


long    CKeywords::GetKeywordReferenceCount(char* theKeyword, short keyLength, Boolean partialMatch)
{
    long    theID;
    long    refCount;

    theID = FindKeywordID(theKeyword, keyLength, partialMatch);
    if (theID > 0)
        refCount = GetKeywordReferenceCount(theID);
    else
        refCount = 0;

    return (refCount);
}


long    CKeywords::FindKeywordID(char* theKeyword, short keyLength, Boolean partialMatch)
{
    BoyerMoore    *theSearcher;
    KeywordPageH    workPage = fFirstKeywordBlock;
    long        foundID = -1;
    long        dataLen;
    Ptr            searchStartP;
    long        foundOffset;
    long        testBlock;

    theSearcher = new BoyerMoore(theKeyword, keyLength);

    while ((workPage != nil) && (foundID == -1))
    {
        HLock((Handle) workPage);

        dataLen = kMaxKeywordsPerPage * sizeof(KeywordHolder);
        foundOffset = 0;    // Special case for loop start
        do {
            dataLen -= foundOffset;
            searchStartP = (Ptr) (*workPage)->keywords;
            theSearcher->SetSearchData(searchStartP + foundOffset, dataLen);
            foundOffset = theSearcher->Search();
            if (foundOffset > 0)        // Figure the block we were in
            {
                testBlock = foundOffset / sizeof(KeywordHolder);
                // Now we need to determine if this is the start of a block
                // We can test the high byte of blockCount and it it is
                // non-zero this block is all text. (A NULL in the middle of
                // a keyword is considered bad form.)
                while ((foundID == -1) && (testBlock >= 0))
                {
                    if (((*workPage)->keywords[testBlock].blockCount && 0xFF00) != 0)    // OK it was bad
                        testBlock--;
                    else {
                            foundID = testBlock;
                            // Now do we meet the partialMatch criteria?
                            if (partialMatch == false)
                            {
                                // Instead of comparing the whole string, I can
                                // get away with comparing the lengths and if they
                                // are the same it is the whole match. (Unless
                                // the search string matched the next block by some
                                // freak of the universe and there were probably
                                // nulls in it!)
                                if ((*workPage)->keywords[testBlock].length != keyLength)
                                {
                                    // Didn't match partialMatch. Set to the start of
                                    // the next block and keep going
                                    foundOffset = (testBlock + 1) * sizeof(KeywordHolder) - 1;
                                    foundID = -1;
                                }
                            }

                         }
                }
                foundOffset++;
            }
        }
        while ((foundOffset > 0) && (foundID == -1));
        HUnlock((Handle) workPage);

        if (foundID == -1)    // Go to the next page
            workPage = (*workPage)->nextPage;
    }

    if (workPage == nil)
        return (0);
    else
        return ((*workPage)->firstKeywordID + foundID + 1);
}


long    CKeywords::FindKeywordIDInRange(long startID, long endID, char* theKeyword, short keyLength, Boolean partialMatch)
{

}


short    CKeywords::GetKeywordByID(long keywordID, char* keyOut)
{
    long    whichPage;
    long    whichItem;
    KeywordPageH    workPage;
    KeywordHolderP    workKeywordP;
    short    length;
    Boolean    gotPage;

    keywordID -= 1;        // Zero base for internal use

    whichPage = keywordID / kMaxKeywordsPerPage;

    gotPage = GetPageN(whichPage, &workPage, false);
    if (gotPage == false)            // Whoops, the ID is out of range!
        return (0);

    whichItem = keywordID % kMaxKeywordsPerPage;

    // Now we have the specified page in workPage
    // Notice that we are NOT locking the page so if we
    // do something stupid like moving memory workKeywordP
    // could end up really invalid
    workKeywordP = &(*workPage)->keywords[whichItem];
    length = workKeywordP->length;
    if ((length > 0) && (keyOut != nil))
    {
        // If block move moves relocatable blocks around under us
        // the entire OS will die, so this is safe
        // And we use BlockMoveData to prevent cache flushing on
        // some machines (68040 specifically)
        BlockMoveData(workKeywordP->keywordData, keyOut, length);
    }

    return (length);
}


// The following routines are used to add keywords
long    CKeywords::AddKeyword(char* theKeyword, short keyLength)
{
    short    requiredBlocks = 1;        // Always need at least one
    short    tempLength;
    KeywordPageH    outPage;
    short            pageIndex;
    KeywordHolderP    keywordP;
    long    theID;
    short    pageNumber;

    tempLength = keyLength - kCharsInFirstKeywordlock;
    while (tempLength > 0)
    {
        requiredBlocks++;
        tempLength -= sizeof(KeywordHolder);    // Subtracting size of extra blocks
    }

    FindAvailableSlot(requiredBlocks, &outPage, &pageIndex, &pageNumber);
    if (pageIndex >= 0)
    {
        // Now I know where to store the keyword, so I need to save it now.
        keywordP = &(*outPage)->keywords[pageIndex];
        keywordP->blockCount = requiredBlocks;
        keywordP->length = keyLength;
        BlockMove(keywordP->keywordData, theKeyword, keyLength);

        // Now I just need to update the block map
        UpdateBlockMap(outPage, pageIndex, requiredBlocks, true);
    }
    else
        return (-1);

    fTotalKeywords++;

    // Now figure out what the ID is
    theID = (pageNumber * kMaxKeywordsPerPage) + pageIndex + 1;
    return (theID);
}


Boolean    CKeywords::AddKeywordReference(long keywordID, long* keyReferenceBlock,
                                short referenceCount)
{

}


void    CKeywords::AddReferenceToAllKeywords(long *keyReferenceBlock);

// And of course you might want to delete a keyword
void    CKeywords::DeleteKeywordID(long keywordID)
{
    long            whichPage;
    long            whichItem;
    Boolean            gotPage;
    KeywordPageH    workPage;
    short            count;

    keywordID -= 1;        // Zero base for internal use

    whichPage = keywordID / kMaxKeywordsPerPage;

    gotPage = GetPageN(whichPage, &workPage, false);
    if (gotPage == false)            // Whoops, the ID is out of range!
        return;

    whichItem = keywordID % kMaxKeywordsPerPage;

    count = (*workPage)->keywords[whichItem].blockCount;
    if (fReuseEmptyHoles)
        UpdateBlockMap(workPage, whichItem, count, false);

    // Now delete the references for this keyword
}


void    CKeywords::DeleteKeywordReference(long keywordID, long* keyReferenceBlock)
{

}


void    CKeywords::DeleteAllReferenceMatch(long *keyReferenceBlock)
{

}


void    CKeywords::DeleteAllReferences(void)
{

}


// Use this with extreme caution! It nukes references, keyword, everything
void    CKeywords::DeleteAllKeywords(void)
{
    KeywordPageH    nextHandle = fFirstKeywordBlock;
    KeywordPageH    currentHandle;

    while (nextHandle != nil)
    {
        currentHandle = nextHandle;
        nextHandle = (*(KeywordPageH)currentHandle)->nextPage;
        DisposeHandle((Handle) currentHandle);
    }

    fFirstKeywordBlock = nil;
}


KeywordPageH    CKeywords::CreateEmptyPage(long firstID)
{
    KeywordPageH    thePage;

    thePage = (KeywordPageH) NewHandleClear(sizeof(KeywordPage));
    if (thePage != nil)
    {
        (*thePage)->firstKeywordID = firstID;
        // Every other field has been zeroed when it was created
    }

    return (thePage);
}


Boolean    CKeywords::GetPageN(short whichPage, KeywordPageH *outHand, Boolean createIt)
{
    KeywordPageH    currentPage = fFirstKeywordBlock;
    KeywordPageH    nextPage = fFirstKeywordBlock;

    while (whichPage > 0)
    {
        if (currentPage != nil)
        {
            nextPage = (*currentPage)->nextPage;
            // Now nextPage doesn't exist yet, if whichPage is 1 and
            // and createIt is true, then make a next page
            // otherwise, we go back empty handled
            if (nextPage == nil)
            {
                if ((whichPage == 1) && (createIt))
                {
                    nextPage = CreateEmptyPage(whichPage * kMaxKeywordsPerPage);
                    (*currentPage)->nextPage = nextPage;
                }
                else {
                        // bad news. We can't or won't create the page
                        currentPage = nil;
                        break;
                     }
            }
        }
        else
            break;    // Leave the loop NOW if currentPage is nil

        currentPage = nextPage;
        whichPage--;
    }

    *outHand = currentPage;

    return (currentPage != nil);
}


void    CKeywords::FindAvailableSlot(short requiredBlocks, KeywordPageH *outPage,
                                        short *pageIndex, short *pageNumber)
{
    KeywordPageH    currentPage;
    KeywordPageH    nextPage;
    Boolean            madeFirstPage = false;    // Special case for empty object
    Boolean            foundSlot;
    short            targetBlock = -1;
    short            whichPage = 0;

    if (fFirstKeywordBlock == nil)
    {
        madeFirstPage = true;
    }

    nextPage = fFirstKeywordBlock;
    foundSlot = false;

    while (!foundSlot)
    {
        if (nextPage == nil)
        {
            nextPage = CreateEmptyPage(0);
            if (nextPage == nil)        // Bad things have just happened.
            {
                *outPage = nil;
                *pageIndex = -1;
            }
            else {
                    // OK, we made a page, better save it to the list
                    if (madeFirstPage)
                        fFirstKeywordBlock = nextPage;
                    else {
                            (*currentPage)->nextPage = nextPage;
                         }

                    if (requiredBlocks > kMaxKeywordsPerPage) // IT BETTER NOT BE
                     {
                         *outPage = nil;
                         *pageIndex = -1;
                     }
                    else {

                            *outPage = nextPage;
                            *pageIndex = 0;
                         }
                 }
            foundSlot = true;    // One way or another we are done now
        }

        currentPage = nextPage;
        if (currentPage != nil)
            nextPage = (*currentPage)->nextPage;

        // OK, now let's see if there is a free space in this page
        targetBlock = FindSlotsOnPage(currentPage, requiredBlocks);
        if (targetBlock > 0)
        {
            foundSlot = true;
        }
        else        // Update the page if this doesn't fit on the page
            whichPage++;
    }

    // Now currentPage has been setup as NIL (unfound) or a legitimate page
    *outPage = currentPage;
    *pageIndex = targetBlock;
    *pageNumber = whichPage;
}


short    CKeywords::FindSlotsOnPage(KeywordPageH currentPage, short blocksRequired)
{
    // THIS IS VERY INEFFICIENT FOR NOW, BUT IT WORKS. THIS SHOULD
    // BE CHANGED TO A FASTER ALGORITHM IN THE NEAR FUTURE
    long    limit;
    long    i, j;
    long    theBit;
    unsigned long    mask;
    short    blocksStillToMatch;
    short    potentialSite = -1;    // Zero based into they keyword map
    long    bitsInThisLong;
    unsigned long    currentLong;

    limit = (kMaxKeywordsPerPage / kBitsInALong) + ( (kMaxKeywordsPerPage % kBitsInALong) ? 1 : 0);

    blocksStillToMatch = blocksRequired;
    for (i = 0; i < limit; i++)
    {
        // i is the long we are currently testing.
        // theBit is the actual bit (up to kMaxKeywordsPerPage) we are testing
        mask = 0x80000000;    // Reset this at the start of each long
        currentLong = (*currentPage)->blockMap[i];

        if (i == (limit - 1))    // On the last long, may be fewer bits
            bitsInThisLong = kMaxKeywordsPerPage % kBitsInALong;
        else
            bitsInThisLong = kBitsInALong;

        for (j = 0; j < bitsInThisLong; j++, mask >>= 1)    // Bits per long
        {
            if ((currentLong & mask) == 0)    // Hey this is an empty hole!
            {
                blocksStillToMatch--;
                potentialSite = (i * kBitsInALong) + j;
            }
            else {
                    blocksStillToMatch = blocksRequired;
                    potentialSite = -1;
                 }

            if (blocksStillToMatch == 0)    // Success!!!
            {
                j = kBitsInALong;    // This is always good, even on the last partial long
                i = limit;

                // And potentialSite has the first bit/block to set
            }
        }
    }

    if (blocksStillToMatch == 0)    // Ran out of page to search when we
        potentialSite = -1;            // were actually matching!

    return (potentialSite);
}


void    CKeywords::UpdateBlockMap(KeywordPageH thePage, short firstBlock, short count, Boolean turnOn)
{
    short    whichLong = firstBlock / kBitsInALong;
    short    firstBit = firstBlock % kBitsInALong;
    unsigned long    mask;
    short    workCount;

    workCount = count;
    mask = 0;

    while (workCount > 0)
    {
        mask = (mask >> 1) || 0x80000000;    // Set the bits in the mask
        workCount--;
    }

    mask >>= firstBit;    // now move the mask into position
    if (turnOn == false)
    {
        mask = ~mask;    // Invert the entire mask
        (*thePage)->blockMap[whichLong] & mask;    // This clears it OK
    }
    else {
            (*thePage)->blockMap[whichLong] | mask;    // This sets the bits
         }

    workCount = (firstBit + (count - 1)) - kBitsInALong;
    if (workCount > 0)
    {
        // Nuts we have a block that rolls over more than 1 byte
        // How many bits do we need set now? (It is in workCount)
        whichLong++;        // Go to the next word
        mask = 0;
        while (workCount > 0)
        {
            mask = (mask >> 1) || 0x80000000;    // Set the bits in the mask
            workCount--;
        }

        if (turnOn == false)
        {
            mask = ~mask;    // Invert the entire mask
            (*thePage)->blockMap[whichLong] & mask;    // This clears it OK
        }
        else {
                (*thePage)->blockMap[whichLong] | mask;    // This sets the bits
             }

    }
}